package com.xieyong.leetcode;

public class Leetcode2044 {

    public static void main(String[] args) {
        Leetcode2044 leetcode2044 = new Leetcode2044();
        int[] nums = {3,1};
        int i = leetcode2044.countMaxOrSubsets(nums);
        System.out.println(i);
    }

    public int countMaxOrSubsets(int[] nums) {
        // 尝试dfs暴力
        // 1.首先对nums所有元素或得到一个最大值
        int max = 0;
        for (int num : nums) {
            max |= num;
        }
        // 2.dfs所有情况, 可选或可不选
        return dfs(0, nums, 0, max);
    }

    private int dfs(int curIndex, int[] nums, int curValue, int max) {
        if (curIndex == nums.length) {
            return curValue == max ? 1 : 0;
        }
        return dfs(curIndex + 1, nums, curValue | nums[curIndex], max) + dfs(curIndex + 1, nums, curValue, max);
    }
}
